package leetcode_100;

/**
 * 2018年5月16日 下午6:46:39
 * @author 周杨
 * MaximalRectangle_85 在一个矩阵中确定连续的最大矩形 并返回其面积
 * describe :用动归数组记录当前坐标延伸的最大面积 AC 98%
 *
 */
public class MaximalRectangle_85 {
	int width[][];
	int height[][];
	public static void main(String[] args) {
		MaximalRectangle_85 test=new MaximalRectangle_85();
		char matrix[][]=new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},
				{'1','1','1','1','1'},{'1','0','0','1','0'}};
		char matrix1[][]=new char[][]{{'0'},{'1'}};
		char matrix2[][]=new char[][]{{'0','1','1','0','1'},{'1','1','0','1','0'},
				{'0','1','1','1','0'},{'1','1','1','1','0'},{'1','1','1','1','1'},{'0','0','0','0','0'}};
		System.out.println(test.maximalRectangle1(matrix2));
	}
	public int maximalRectangle(char[][] matrix) {
       if(matrix.length==0||matrix[0].length==0)
       	return 0;
       this.width=new int[matrix.length][matrix[0].length];
       this.height=new int[matrix.length][matrix[0].length];
       width[0][0]=matrix[0][0]=='0'?0:1;
       height[0][0]=width[0][0];
       int max=width[0][0];
       for(int row=1;row<matrix.length;++row){
    	   if(matrix[row][0]!='0'){
    		   height[row][0]=height[row-1][0]+1;
    		   width[row][0]=matrix[row][0]-'0';
    		   max=Math.max(max, Math.max(height[row][0],width[row][0]));
    	   }
       }
       for(int col=1;col<matrix[0].length;++col)
    	   if(matrix[0][col]!='0'){
    		   width[0][col]=width[0][col-1]+1;
    		   height[0][col]=matrix[0][col]-'0';
    		   max=Math.max(max, Math.max(height[0][col],width[0][col]));
    	   }
       for(int row=1;row<matrix.length;++row){
    	   for(int col=1;col<matrix[0].length;++col){
    		   if(matrix[row][col]!='0'){
    			   height[row][col]=height[row-1][col]+1;
    			   width[row][col]=width[row][col-1]+1;
    			   max=Math.max(max, Math.max(height[row][col], width[row][col]));
    			   int val=height[row][col]*width[row][col];//理论上的值
    			   if(val<=max){
    				   continue;
    			   }
    			   else{
    				   int minWidth=width[row][col];
    				   int minHeight=height[row][col];
    				   while(minHeight>1){
	    				   for(int i=1;i<minHeight;++i){//在宽度矩阵中查找最小宽度  查询长度为当前长度
	    					   if(width[row-i][col]<minWidth){
	    						   minWidth=width[row-i][col];
	    						   if(minWidth*height[row][col]<=max)
	    							   break;
	    					   }
	    				   }
	    				   
	    				   for(int i=1;i<minWidth;++i){
	    					   if(height[row][col-i]<minHeight){
	    						   minHeight=height[row][col-i];
	    						   if(minHeight*minWidth<=max)
	    							   break;
	    					   }
	    				   }
	    				   max=Math.max(max, minHeight*minWidth);
	    				   --minHeight;
    				   }
    			   }
    		   }
    			   
    	   }
       }
       return max;
    }
	/**
	 * @param matrix 用动态规划的方式解决 每次只储存i j处能延伸的最大矩阵
	 * @return
	 */
	public int maximalRectangle1(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0] == null) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[] l = new int[n];
        int[] r = new int[n];
        int[] h = new int[n];
        int result = 0;

        for(int i = 0; i < n; i++){
            l[i] = 0;
            r[i] = n;
            h[i] = 0;
        }
        for(int i = 0; i < m; i++){
            int cur_left = 0, cur_right = n;//保存当前行 某一个数能延伸的最大数值
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1') h[j] += 1;
                else                    h[j] = 0;//确定此处向上延伸的最大高度
            }
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == '1'){
                    l[j] = Math.max(l[j], cur_left);//如果上一行有数  则会影响下一行的延伸
                }
                else{
                    l[j] = 0;
                    cur_left = j + 1;
                }
            }
            for(int j = n-1; j >= 0; j--){
                if(matrix[i][j] == '1'){
                    r[j] = Math.min(r[j], cur_right);
                }
                else{
                    r[j] = n;
                    cur_right = j;
                }
            }
            for(int j = 0; j < n; j++){
                result = Math.max(result, (r[j] - l[j]) * h[j]);
            }
        }
        return result;
    }
}
